package org.example.algorithm.dp;

import java.util.Arrays;

public class CoinChange2Solution {
    private int count;

    public static void main(String[] args) {
        int[] coins = {1,2,5};
        int amount = 5;
        CoinChange2Solution solution = new CoinChange2Solution();
        int res = solution.change(amount, coins);
        System.out.println(res);
    }

    public int change(int amount, int[] coins) {
        int len = coins.length;
        int[][] memo = new int[len][amount+1];
        for (int[] item: memo) {
            Arrays.fill(item, -1);
        }
        memo[0][0] = 1;
        return dfs(amount, coins, len-1, memo);
    }

    private int dfs(int amount, int[] coins, int index, int[][] memo) {
        if (index < 0) {
            return amount == 0 ? 1 : 0;
        }
        if (coins[index] > amount) {
            return memo[index][amount] = dfs(amount, coins, index-1, memo);
        }
        return  memo[index][amount] = dfs(amount, coins, index-1, memo) + dfs(amount-coins[index], coins, index, memo);
    }

    //优化内存占用
    public int change1(int amount, int[] coins) {
        if (coins == null || coins.length == 0) {
            return 0;
        }
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for (int i=1;i<=coins.length;i++) {
            for (int j=0;j<=amount;j++) {
                if (coins[i-1] <= j) {
                    dp[j] += dp[j-coins[i-1]];
                }
            }
        }
        return dp[amount];
    }

    //错误思路:dp[i]代表和为i的最大组合数, dp[i] = dp[i-coins[j]]各种情况累加，这种情况下会重复计算
    //正确思路:dp[i][j]代表前i种货币和为j的最大组合数, dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]
    public int change2(int amount, int[] coins) {
        if (coins == null || coins.length == 0) {
            return 0;
        }
        int[][] dp = new int[coins.length+1][amount+1];
        for (int i=0;i<=coins.length;i++) {
            dp[i][0] = 1;
        }
        for (int i=1;i<=coins.length;i++) {
            for (int j=0;j<=amount;j++) {
                if (coins[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[coins.length][amount];
    }
}
